/FONT#0=BASL30/FONT#1=BASI30
␈↓␈↓↓␈↓LISP Functions and Programs for Game Playing
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓ α_These␈αprograms␈αcomprise␈αthree␈αpairs␈αof␈αfunctions␈αand␈αthe␈αcommon␈αprogram␈αRECTIFY␈αwith
␈↓ ↓Hits␈α↔satellites␈α↔COMMONTAIL␈α↔and␈α↔COMMONHEAD.␈α⊗The␈α⊗pairs␈α⊗are␈α⊗(VALMAX,VALMIN),
␈↓ ↓H(LINEMAX,LINEMIN),␈α
and␈α(TREEMAX,TREEMIN).␈αThe␈αprograms␈αof␈αeach␈αpair␈αcall␈αeach␈αother
␈↓ ↓Hand␈α∞differ␈α∞only␈α∞in␈α∞that␈α∞one␈α∞is␈α∞for␈α∞a␈α∞position␈α∞in␈α∞which␈α∞the␈α∞maximizing␈α
player␈α
is␈α
to␈α
move␈α
and␈α
the
␈↓ ↓Hother␈αis␈αfor␈αwhen␈αthe␈αminimizer␈αis␈αto␈αmove.␈αVALMAX␈αand␈αVALMIN␈αgive␈αthe␈αvalue␈αof␈αthe␈αgame,
␈↓ ↓HLINEMAX␈αand␈αLINEMIN␈αgive␈αthe␈αvalue␈αand␈αthe␈αmain␈αline␈αof␈αplay,␈αi.e.␈αwhat␈αwill␈αhappen␈αif␈αboth
␈↓ ↓Hplayers␈αuse␈αtheir␈αbest␈αmoves,␈αand␈αTREEMAX␈αand␈αTREEMIN␈αgive␈αa␈αproof␈αtree␈αthat␈αthe␈αgame␈αhas
␈↓ ↓Hthe␈α∞value␈α∞found.␈α∞This␈α∞proof␈α∞tree␈α∞consists␈α∞of␈α
those␈α
positions␈α
that␈α
would␈α
be␈α
examined␈α
if␈α
the␈α
moves
␈↓ ↓Hhad␈α
been␈α
looked␈α
at␈α
in␈α
the␈α
best␈α
order.

␈↓ α_Positions␈α∞are␈α∞represented␈α∞to␈α∞these␈α∞functions␈α
by␈α
the␈α
sequence␈α
of␈α
moves␈α
leading␈α
to␈α
them␈α
from
␈↓ ↓Hthe␈α
beginning␈α
of␈α
the␈α
game␈α
in␈α
reverse␈α
order.␈α
This␈α
is␈α
economical␈α
of␈α
storage,␈αbecause␈αmany␈αpositions
␈↓ ↓Hwith␈α∂the␈α∂same␈α∂initial␈α∂segment␈α∂can␈α∂be␈α∂represented␈α∂as␈α∂merging␈α∂list␈α∂structures.␈α∞The␈α∞particular␈α∞game
␈↓ ↓Hbeing␈α⊃played␈α⊃is␈α⊃embodied␈α⊃in␈α⊃the␈α⊃functions␈α⊃SUCCESSORS,␈α⊃TER,␈α⊃and␈α⊂IMVAL␈α⊂which␈α⊂give␈α⊂the
␈↓ ↓Hsuccessor␈α⊃positions␈α⊃of␈α⊃a␈α⊃position,␈α⊃tell␈α⊃whether␈α⊃the␈α⊃postion␈α⊃is␈α⊃terminal,␈α⊃and␈α⊃if␈α⊃so␈α⊃give␈α⊃its␈α⊃value.
␈↓ ↓HRECTIFY␈αis␈αa␈αthe␈αidentity␈αfunction␈αused␈αfor␈αa␈αside␈αeffect.␈αThe␈αidea␈αis␈αthat␈αit␈αis␈αusually␈αconvenient
␈↓ ↓Hin␈αcomputing␈αthe␈αsuccessors,␈αetc.␈αto␈αrepresent␈αpositions␈αother␈αthan␈αas␈αa␈αlist␈αof␈αmoves,␈αe.g.␈αas␈αa␈αset␈αof
␈↓ ↓Htables.␈α⊃Associated␈α⊂with␈α⊂a␈α⊂position␈α⊂is␈α⊂a␈α⊂set␈α⊂of␈α⊂tables␈α⊂and␈α⊂a␈α⊂list␈α⊂of␈α⊂moves␈α⊂leading␈α⊂to␈α⊂the␈α⊂position
␈↓ ↓Hrepresented␈αin␈αthe␈αtables.␈αVALMAX␈αetc.␈αget␈αnew␈αpositions␈αby␈α␈↓↓cons␈↓ing␈αmoves␈αonto␈αold␈αpositions␈αand
␈↓ ↓Hby␈α∞␈↓↓cdr␈↓ing␈α
to␈α
revert.␈α
RECTIFY␈α
applied␈α
to␈α
the␈α
list␈α
representing␈α
a␈α
position␈α
returns␈α
the␈α
same␈α
list␈α
but
␈↓ ↓Hreadjusts␈α↔the␈α↔tables␈α↔to␈α↔correspond␈α⊗to␈α⊗the␈α⊗postion␈α⊗given␈α⊗by␈α⊗the␈α⊗list.␈α⊗In␈α⊗doing␈α⊗this␈α⊗it␈α⊗uses
␈↓ ↓HCOMMONTAIL␈α~to␈α~determine␈α→what␈α→moves␈α→to␈α→take␈α→back␈α→and␈α→game␈α→dependent␈α→programs
␈↓ ↓HUPDATE(move)␈α
and␈α
REVERT␈α
in␈α
order␈α
to␈α
make␈α
the␈α
adjustments.

␈↓ α_The␈α∃purpose␈α∃of␈α∀these␈α∀programs␈α∀is␈α∀to␈α∀illustrate␈α∀the␈α∀recursive␈α∀structure␈α∀of␈α∀this␈α∀kind␈α∀of
␈↓ ↓Hcalculation␈α∂in␈α∂a␈α∂way␈α∂independent␈α∂of␈α∂the␈α∂particular␈α∂game.␈α∂Some␈α∂additional␈α∂heuristics,␈α∞such␈α∞as␈α∞the
␈↓ ↓H␈↓↓killer␈↓␈α
heuristic␈α
can␈α
also␈α
be␈α
put␈α
in␈α
this␈α
game␈α
independent␈α
form.

␈↓ α_The␈α
functions␈α
SUCCESSORS,␈α
TER,␈α
IMVAL,␈α
UPDATE,␈α
and␈α
REVERT␈α
are␈α
available␈α
in␈α
files
␈↓ ↓Hfor␈α
the␈α
game␈α
of␈α
tictactoe.